% 在本地编译时，采用XeLaTeX编译，pdfLaTeX可能编译失败

\documentclass[11pt]{article}
\usepackage{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

\usepackage{ctex}
\usepackage{comment}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{diagbox}
\usepackage{amsmath,amsfonts,graphicx,amssymb,bm,amsthm}
\usepackage{algorithm,algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{fancyhdr}
\usepackage{tikz}
\usepackage{graphicx}
\usetikzlibrary{arrows,automata}
\usepackage{hyperref}
%以下是对latex插入代码块的头文件内容
\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3
}
%以上是对latex插入代码块的头文件内容



\setlength{\headheight}{14pt}

\newcounter{counter_exm}\setcounter{counter_exm}{1}
%\newcounter{counter_thm}\setcounter{counter_thm}{1}
%\newcounter{counter_lma}\setcounter{counter_lma}{1}
%\newcounter{counter_dft}\setcounter{counter_dft}{1}
%\newcounter{counter_clm}\setcounter{counter_clm}{1}
%\newcounter{counter_cly}\setcounter{counter_cly}{1}

\newtheorem{theorem}{\hskip 1.7em 定理}
\newtheorem{lemma}[theorem]{\hskip 1.7em 引理}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{\hskip 1.7em 命题}
\newtheorem{corollary}[theorem]{\hskip 1.7em 推论}
\newtheorem{definition}[theorem]{\hskip 1.7em 定义}

\renewcommand{\emph}[1]{\begin{kaishu}#1\end{kaishu}}

\newenvironment{solution}{{\noindent\hskip 2em \bf 解 \quad}}


\renewenvironment{proof}{{\noindent\hskip 2em \bf 证明 \quad}}{\hfill$\qed$\par}
\newenvironment{example}{{\noindent\hskip 2em \bf 例 \arabic{counter_exm}\quad}}{\addtocounter{counter_exm}{1}\par}

\newenvironment{concept}[1]{{\bf #1\quad} \begin{kaishu}} {\end{kaishu}\par}

\newcommand\E{\mathbb{E}}

% 以上是预定义宏等设置,在不熟悉LaTeX的情况下可不作修改.

% TODO: 在此处更改第X讲
\title{算法设计初步第X讲}
\usetikzlibrary{positioning}

\begin{document}

    \pagestyle{fancy}
    \lhead{\kaishu 杭州师范大学}
    \chead{}
    \rhead{\kaishu 2020年秋季学期算法设计初步}

    % TODO: 在此处更改第X讲、授课时间与记录人
    \begin{center}
        {\LARGE \bf 算法设计初步第二次上机作业}\\
    \end{center}
        \begin{kaishu}
            授课时间: 2020年11月10日\quad
            授课教师: 张仁军
            \hfill 提交人: 范吉祥
        \end{kaishu}
    
    %%%%%%%%%%%%%%%%%%%%% Your note starts from here %%%%%%%%%%%%%%%%%%%%%

    \section{作业描述}
    
    \begin{itemize}
        \subsection{题目描述}
        \item 考虑一种新的逆序对定义: 如果 i < j 并且 A[i] > 3A[j]，则称这样的一对数为逆序对. 设计一个算法
        计算数组中这种逆序对的个数，要求算法的运行时间为 O(n log n).
           
    \end{itemize}
    \section{答案}
    \begin{itemize}
        \subsection{尝试} 
        \item 
        \begin{lstlisting}
            def mysort(lst):
                if len(lst) == 1:
                    return lst,0
                else:
                    n = len(lst) // 2#提取中间数
                    lst1,count1 = mysort(lst[0:n])#获得左侧数组，带入递归
                    lst2,count2 = mysort(lst[n:len(lst)+1])#获得右侧数组，带入递归
                    lst,count = sortandcount(lst1,lst2,0)#讲左侧右侧数组带入sortandcount进行排序以及逆序数的计数
                    return lst,count1+count2+count
         
        def sortandcount(lst1, lst2,count): 
            i = 0#初始化左侧数组索引
            j = 0#初始化右侧数组索引
            res = []#存储经过排列后的
            while i < len(lst1) and j < len(lst2):#当索引不超过两个列表长度的情况下进行循环
                if lst1[i] <= lst2[j]:
                    res.append(lst1[i])
                    i += 1
                else:
                    if lst1[i]>3*lst2[j]:
                        count += len(lst1)-i
                    res.append(lst2[j])
                    j += 1
            res += lst1[i:]
            res += lst2[j:]
            return res,count
        print(mysort([15,6,50,12,1,90])) 

        ([1, 6, 12, 15, 50, 90], 4)
 \end{lstlisting}
        \subsection{分析}
        \subsubsection{算法设计思想} 
        \item 采用分治思想，选取中间数，将整个数组分成左右部分，不断进行递归，递归时根据计算逆序数
        \subsubsection{算法正确性分析}
        \item 采用分治思想，通过整除获得数组的中间数的索引，将一个列表分成左侧和右侧两个子列表，进行递归，直到子列表的长度为1，停止递归。每次递归的结果进行排序，排序时统计逆序数，即当左右列表的索引在不超过列表长度的情况下，从索引为0开始比较，若左侧列表内元素大于三倍的右侧元素，则count增加了左侧列表长度减去索引的数，因为左右列表均已排序，如果左侧列表元素大于右侧的某个元素，则左侧列表之后索引的元素均满足逆序数的定义，最后将两个子列表整合成一个列表，完成递归。
        \subsubsection{时间复杂度}
        \item  由于分治思想，故时间复杂度为$nlog_{2}^{n}$
               
    \end{itemize}
    


    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%% End %%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
\end{document}